package com.algorithm.learning.base.动态规划;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: algorithm-learning
 * @description:
 * @author: YuKai Fan
 * @create: 2024/9/2 22:11
 **/
public class 打印字符串的所有子序列 {

    public static void main(String[] args) {
        List<String> ans = subs("abc");
        for (String str : ans) {
            System.out.println(str);
        }
    }

    public static List<String> subs(String s) {
        char[] str = s.toCharArray();
        String path = "";
        List<String> ans = new ArrayList<>();
        process1(str, 0, ans, path);
        return ans;
    }

    /**
     * 什么是子序列？
     * 一个字符串的子序列可以从任意字符的组合，但是必须满足原本字符串的字符栓寻
     *
     * 例如有一个字符串：abcd，它的子序列可以是：ab, ac, ad, abc, abcd, acd, abd, bc, bd...
     *
     * 但是不允许出现：ba, da, db, dc等，不满足字符串的原本字符的顺序
     *
     * 参考 => /img/打印字符串的所有子序列_1.png
     */
    public static void process1(char[] str, int index, List<String> ans, String path) {
        if (index == str.length) {
            ans.add(path);
            return;
        }
        String no = path;
        process1(str, index + 1, ans, no);
        String yes = path + str[index];
        process1(str, index + 1, ans, yes);

    }
}
